// https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// 34. 在排序数组中查找元素的第一个和最后一个位置
// 给定一个按照升序排列的整数数组 nums，和一个目标值 target，找出给定目标
// 值在数组中的开始位置和结束位置。
// 如果数组中不存在目标值 target，返回 [-1, -1]
function searchRange(nums: number[], target: number): number[] {
    if (nums.length === 0) return [-1, -1];

    const start = getStartPosition(nums, target);
    if (start === -1) {
        return [-1, -1];
    }

    const last = getLastPosition(nums, target);
    return [start, last];

    function getStartPosition(nums: number[], target: number): number {
        let left = 0,
            right = nums.length - 1;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] === target) {
                right = mid;
            } else {
                right = mid - 1;
            }
        }

        if (nums[left] === target) return left;
        return -1;
    }

    function getLastPosition(nums: number[], target: number): number {
        let left = 0,
            right = nums.length - 1;
        while (left < right) {
            const mid = (left + right + 1) >> 1;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] === target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
}
